#include <cstdio>

using namespace std;

int temp[10005] = {0};
void display(int arr[], int start ,int len) {
	for (int i = start; i < len; i++)
	{
		printf("%8d",arr[i]);
	}
	printf("\n");
}
void merge_sort(int arr[],int start,int mid,int len) {

	for (int i = start; i <= len; i++)
	{
		temp[i-start] = arr[i];
	}
	int j = start, k = mid + 1;
	for (int i = start; i <= len; i++)
	{
		//左数组都已进入新数组
		if (j>mid)
		{
			arr[i] = temp[k - start];
			k++;
		}
		//右数组都已进入新数组
		else if (k>len)
		{
			arr[i] = temp[j - start];
			j++;
		}
		else if (temp[j-start] < temp[k-start])
		{
			arr[i] = temp[j - start];
			j++;
		}
		else
		{
			arr[i] = temp[k - start];
			k++;
		}
	}
}

void merge_splic(int arr[],int start,int len) {

	if (start >= len)
	{
		return;
	}
	int mid = (start + len) / 2;
	merge_splic(arr, start, mid);
	merge_splic(arr, mid + 1, len);

	merge_sort(arr,start,mid,len);
}
void merge (int arr[],int start,int len) {
	merge_splic(arr,start,len-1);
}
int main() {

	int arr[] = {111,2,3,4,6,454,66,5666,5656,654656,365656,222,4444,88888};
	int len = sizeof(arr) / sizeof(int);
	display(arr, 0, len);
	merge(arr,0,len);
	display(arr, 0, len);
	return 0;
}